//{==================================================================================================
//! @file Summ4.cpp
//! @date 2013-09-29
//! @mainpage Program for verifing the existence of the expansion by a linear combination
//! @author Kirill Shcherbatov <kshcherbatov@gmail.com>, 376 group, DCAM MIPT
//! @version 1.0
//! @note Task C, varriant 1, test 2007, MIPT
//}===================================================================================================

//****************************************************************************************************
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//****************************************************************************************************

//****************************************************************************************************
#define _EJC
#define PARANOIC_MODE
//****************************************************************************************************

//****************************************************************************************************
//! @def   OUT
//! @note  -Use OUT to print your text in console. It is checking _EJC declaration.
//! @note  -Only if _EJC is defined then the program prints your text.
//! @note  --You also can define _EJC in compilation command (g++ main.cpp -D _EJC)
//----------------------------------------------------------------------------------------------------
#ifdef _EJC
    #define OUT printf
#else
    #define OUT if (0) printf
#endif // _EJC
//****************************************************************************************************


//****************************************************************************************************
//! @def    VALID
//! @param  CONDITIONAL for checking
//! @param  MESSAGE for displaying if CONDITIONAL is false
//! @note   -It checks the validity of the expression.
//! @note   -Program will use OUT to display MESSAGE
//! @note   -If sended conditional is false, program will be terminated sending 1 message
//----------------------------------------------------------------------------------------------------
#ifdef  PARANOIC_MODE
    #define VALID( CONDITIONAL, MESSAGE )       \
    if (!(CONDITIONAL))                         \
    {                                           \
        OUT  ( MESSAGE );                       \
        exit ( 1 );                             \
    } // VALID in PARANOIC_MODE
#else
    #define VALID( CONDITIONAL, MESSAGE ) \
    CONDITIONAL;
#endif
//****************************************************************************************************

//****************************************************************************************************
//! @def    CHECK
//! @param  CONDITIONAL for checking
//! @param  MESSAGE for displaying if CONDITIONAL is false
//! @note   -It checks the validity of the expression.
//! @note   -Program will use OUT to display MESSAGE
//! @note   -If sended conditional is false, program will be terminated sending 1 message
//! @warning   IN RELIASE MODE IT WILL BE REMOOVED
//----------------------------------------------------------------------------------------------------
#ifdef PARANOIC_MODE
    #define CHECK( CONDITIONAL, MESSAGE )       \
    if (!(CONDITIONAL))                         \
    {                                           \
        OUT  ( MESSAGE );                       \
        exit ( 1 );                            \
    } // CHECK in PARANOIC_MODE
#else
    #define CHECK( CONDITIONAL, MESSAGE )
#endif
//****************************************************************************************************

//****************************************************************************************************
int IsFreeBySqr(unsigned long long int N);
//****************************************************************************************************


//****************************************************************************************************
//! @param - number of sending arguments
//! @param argv[] - arguments, include generated by OS
//! @return 0 on success
//----------------------------------------------------------------------------------------------------
int main(int, const char* argv[])
{
    OUT ("%s (%s) %s %s:\n\n", argv[ 0 ], __FILE__, __DATE__, __TIME__);
    OUT ("#Program for verifing the existence of\n");
    OUT ("#the expansion by a linear combination\n\n");
    OUT ("#Enter N, the number for researching\n");

    unsigned long long int N = 0;

    OUT ("N=");
    VALID (scanf ("%llu", &N) == 1,  "#Problems with inputed N. Read the instructions above & try again.\n");

    const long long unsigned int N_MAX = 1llu << 31;

    CHECK (N >= 0, "#Inputed N is incorrect. N should be greater than 0.\n");
    CHECK (N < N_MAX, "#Inputed N is incorrect. N should be lower than 10 000.\n");
    OUT ("So, the result is ");
    printf ("%s", (IsFreeBySqr (N) ) ? "YES" : "NO") ;

    return 0;
}
//****************************************************************************************************

//****************************************************************************************************
//! @param    Number for analyzing
//! @return   N 1 if the N "IsFreeBySqr" else 0
//! @note     build dynamic array inicialized as 1->true; linary mark as 0
//! @note     value N should be from half-interval (0; 2^31]
//****************************************************************************************************
int IsFreeBySqr(unsigned long long int N)
{
    char * buffer = (char *)calloc((N+1),sizeof(char));

    CHECK(buffer!=NULL, "b value is NULL!\n");

    for (register char * p = buffer; p<&buffer[N+1]; p++) *p=1;

    for (register char i=0; 4*i<=(N+1); i++)
    {
        register char j=4*i+2;
        if (buffer[j])
        {
            while (j<=(N+1))
            {
                buffer[j]=0;
                j=4*j+2;
            }
        }
    }
    char temp = buffer[N];
    free(buffer);
    buffer = NULL;
    if (temp) return 1; else return 0;
}
//****************************************************************************************************
